home *** CD-ROM | disk | FTP | other *** search
/ Multimedia Jumpstart / Multimedia Microsoft Jumpstart Version 1.1a (Microsoft).BIN / develpmt / sdk / vfw11.win / vfwdk / dibmap.c_ / dibmap.bin
Encoding:
Text File  |  1993-11-19  |  25.9 KB  |  1,031 lines
  1. /**************************************************************************
  2.  *
  3.  *  THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY
  4.  *  KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  5.  *  IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A PARTICULAR
  6.  *  PURPOSE.
  7.  *
  8.  *  Copyright (c) 1992, 1993  Microsoft Corporation.  All Rights Reserved.
  9.  * 
  10.  **************************************************************************/
  11.  
  12. #include <windows.h>
  13. #include <windowsx.h>
  14. #include "dibmap.h"
  15.  
  16. extern NEAR PASCAL MemCopy(LPVOID,LPVOID,DWORD);
  17. extern NEAR PASCAL MemFill(LPVOID,DWORD,BYTE);
  18.  
  19. void Histogram24(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram);
  20. void Histogram16(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram);
  21. void Histogram8(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors);
  22. void Histogram4(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors);
  23. void Histogram1(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors);
  24.  
  25. void Reduce24(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp16to8);
  26. void Reduce16(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp16to8);
  27. void Reduce8(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8);
  28. void Reduce4(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8);
  29. void Reduce1(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8);
  30.  
  31. //
  32. //  InitHistogram
  33. //
  34. //  create a zero'ed histogram table, or initialize a existing table
  35. //  to all zeros.
  36. //
  37. LPHISTOGRAM InitHistogram(LPHISTOGRAM lpHistogram)
  38. {
  39.     if (lpHistogram == NULL)
  40.         lpHistogram = (LPVOID)GlobalAllocPtr(GHND, 32768L * sizeof(DWORD));
  41.  
  42.     return lpHistogram;
  43. }
  44.  
  45. //
  46. //  FreeHistogram
  47. //
  48. //  free a histogram table
  49. //
  50. void FreeHistogram(LPHISTOGRAM lpHistogram)
  51. {
  52.     GlobalFreePtr(lpHistogram);
  53. }
  54.  
  55. //
  56. //  DibHistogram
  57. //
  58. //  take all colors in a dib and increment its entry in the Histogram table
  59. //
  60. //  supports the following DIB formats: 1,4,8,16,24
  61. //
  62. BOOL DibHistogram(LPBITMAPINFOHEADER lpbi, LPBYTE lpBits, int x, int y, int dx, int dy, LPHISTOGRAM lpHistogram)
  63. {
  64.     int             i;
  65.     WORD            WidthBytes;
  66.     RGBQUAD FAR *   prgbq;
  67.     WORD            argb16[256];
  68.  
  69.     if (lpbi == NULL || lpHistogram == NULL)
  70.         return FALSE;
  71.  
  72.     if (lpbi->biClrUsed == 0 && lpbi->biBitCount <= 8)
  73.         lpbi->biClrUsed = (1 << (int)lpbi->biBitCount);
  74.  
  75.     if (lpBits == NULL)
  76.         lpBits = (LPBYTE)lpbi + (int)lpbi->biSize + (int)lpbi->biClrUsed*sizeof(RGBQUAD);
  77.  
  78.     WidthBytes = (WORD)((lpbi->biBitCount * lpbi->biWidth + 7) / 8 + 3) & ~3;
  79.  
  80.     ((BYTE huge *)lpBits) += (DWORD)y*WidthBytes + ((x*(int)lpbi->biBitCount)/8);
  81.  
  82.     if (dx < 0 || dx > (int)lpbi->biWidth)
  83.         dx = (int)lpbi->biWidth;
  84.  
  85.     if (dy < 0 || dy > (int)lpbi->biHeight)
  86.         dy = (int)lpbi->biHeight;
  87.  
  88.     if ((int)lpbi->biBitCount <= 8)
  89.     {
  90.         prgbq = (LPVOID)((LPBYTE)lpbi + lpbi->biSize);
  91.  
  92.         for (i=0; i<(int)lpbi->biClrUsed; i++)
  93.         {
  94.             argb16[i] = RGB16(prgbq[i].rgbRed,prgbq[i].rgbGreen,prgbq[i].rgbBlue);
  95.         }
  96.  
  97.         for (i=(int)lpbi->biClrUsed; i<256; i++)
  98.         {
  99.             argb16[i] = 0x0000;     // just in case!
  100.         }
  101.     }
  102.  
  103.     switch ((int)lpbi->biBitCount)
  104.     {
  105.         case 24:
  106.             Histogram24(lpBits, dx, dy, WidthBytes, lpHistogram);
  107.             break;
  108.  
  109.         case 16:
  110.             Histogram16(lpBits, dx, dy, WidthBytes, lpHistogram);
  111.             break;
  112.  
  113.         case 8:
  114.             Histogram8(lpBits, dx, dy, WidthBytes, lpHistogram, argb16);
  115.             break;
  116.  
  117.         case 4:
  118.             Histogram4(lpBits, dx, dy, WidthBytes, lpHistogram, argb16);
  119.             break;
  120.  
  121.         case 1:
  122.             Histogram1(lpBits, dx, dy, WidthBytes, lpHistogram, argb16);
  123.             break;
  124.     }
  125. }
  126.  
  127. //
  128. // will convert the given DIB to a 8bit DIB with the specifed palette
  129. //
  130. HANDLE DibReduce(LPBITMAPINFOHEADER lpbiIn, LPBYTE pbIn, HPALETTE hpal, LPBYTE lp16to8)
  131. {
  132.     HANDLE              hdib;
  133.     int                 nPalColors;
  134.     int                 nDibColors;
  135.     WORD                cbOut;
  136.     WORD                cbIn;
  137.     BYTE                xlat[256];
  138.     BYTE huge *         pbOut;
  139.     RGBQUAD FAR *       prgb;
  140.     DWORD               dwSize;
  141.     int                 i;
  142.     int                 dx;
  143.     int                 dy;
  144.     PALETTEENTRY        pe;
  145.     LPBITMAPINFOHEADER  lpbiOut;
  146.  
  147.     dx    = (int)lpbiIn->biWidth;
  148.     dy    = (int)lpbiIn->biHeight;
  149.     cbIn  = ((lpbiIn->biBitCount*dx+7)/8+3)&~3;
  150.     cbOut = (dx+3)&~3;
  151.  
  152.     GetObject(hpal, sizeof(int), (LPVOID)&nPalColors);
  153.     nDibColors = (int)lpbiIn->biClrUsed;
  154.  
  155.     if (nDibColors == 0 && lpbiIn->biBitCount <= 8)
  156.         nDibColors = (1 << (int)lpbiIn->biBitCount);
  157.  
  158.     if (pbIn == NULL)
  159.         pbIn = (LPBYTE)lpbiIn + (int)lpbiIn->biSize + nDibColors*sizeof(RGBQUAD);
  160.  
  161.     dwSize = (DWORD)cbOut * dy;
  162.  
  163.     hdib = GlobalAlloc(GMEM_MOVEABLE,sizeof(BITMAPINFOHEADER)
  164.         + nPalColors*sizeof(RGBQUAD) + dwSize);
  165.  
  166.     if (!hdib)
  167.         return NULL;
  168.  
  169.     lpbiOut = (LPVOID)GlobalLock(hdib);
  170.     lpbiOut->biSize         = sizeof(BITMAPINFOHEADER);
  171.     lpbiOut->biWidth        = lpbiIn->biWidth;
  172.     lpbiOut->biHeight       = lpbiIn->biHeight;
  173.     lpbiOut->biPlanes       = 1;
  174.     lpbiOut->biBitCount     = 8;
  175.     lpbiOut->biCompression  = BI_RGB;
  176.     lpbiOut->biSizeImage    = dwSize;
  177.     lpbiOut->biXPelsPerMeter= 0;
  178.     lpbiOut->biYPelsPerMeter= 0;
  179.     lpbiOut->biClrUsed      = nPalColors;
  180.     lpbiOut->biClrImportant = 0;
  181.  
  182.     pbOut = (LPBYTE)lpbiOut + (int)lpbiOut->biSize + nPalColors*sizeof(RGBQUAD);
  183.     prgb  = (LPVOID)((LPBYTE)lpbiOut + (int)lpbiOut->biSize);
  184.  
  185.     for (i=0; i<nPalColors; i++)
  186.     {
  187.         GetPaletteEntries(hpal, i, 1, &pe);
  188.  
  189.         prgb[i].rgbRed      = pe.peRed;
  190.         prgb[i].rgbGreen    = pe.peGreen;
  191.         prgb[i].rgbBlue     = pe.peBlue;
  192.         prgb[i].rgbReserved = 0;
  193.     }
  194.  
  195.     if ((int)lpbiIn->biBitCount <= 8)
  196.     {
  197.         prgb = (LPVOID)((LPBYTE)lpbiIn + lpbiIn->biSize);
  198.  
  199.         for (i=0; i<nDibColors; i++)
  200.             xlat[i] = lp16to8[RGB16(prgb[i].rgbRed,prgb[i].rgbGreen,prgb[i].rgbBlue)];
  201.  
  202.         for (; i<256; i++)
  203.             xlat[i] = 0;
  204.     }
  205.  
  206.     switch ((int)lpbiIn->biBitCount)
  207.     {
  208.         case 24:
  209.             Reduce24(pbIn, dx, dy, cbIn, pbOut, cbOut, lp16to8);
  210.             break;
  211.  
  212.         case 16:
  213.             Reduce16(pbIn, dx, dy, cbIn, pbOut, cbOut, lp16to8);
  214.             break;
  215.  
  216.         case 8:
  217.             Reduce8(pbIn, dx, dy, cbIn, pbOut, cbOut, xlat);
  218.             break;
  219.  
  220.         case 4:
  221.             Reduce4(pbIn, dx, dy, cbIn, pbOut, cbOut, xlat);
  222.             break;
  223.  
  224.         case 1:
  225.             Reduce1(pbIn, dx, dy, cbIn, pbOut, cbOut, xlat);
  226.             break;
  227.     }
  228.  
  229.     return hdib;
  230. }
  231.  
  232. ///////////////////////////////////////////////////////////////////////////////
  233. //  cluster.c
  234. ///////////////////////////////////////////////////////////////////////////////
  235.  
  236. #define  IN_DEPTH    5               // # bits/component kept from input
  237. #define  IN_SIZE     (1 << IN_DEPTH) // max value of a color component
  238.  
  239. typedef enum { red, green, blue } color;
  240.  
  241. typedef struct tagCut {
  242.    long lvariance;        // for int version
  243.    int cutpoint;
  244.    unsigned long rem;        // for experimental fixed point
  245.    color cutaxis;
  246.    long w1, w2;
  247.    double variance;
  248.    } Cut;
  249.  
  250. typedef struct tagColorBox {    // from cluster.c
  251.    struct tagColorBox *next;                /* pointer to next box */
  252.    int   rmin, rmax, gmin, gmax, bmin, bmax;    /* bounding box */
  253.    long variance, wt;                           /* weighted variance */
  254.    long sum[3];                                 /* sum of values */
  255.    } ColorBox;
  256.  
  257. static int InitBoxes(int nBoxes);
  258. static void DeleteBoxes(void);
  259. static int SplitBoxAxis(ColorBox *box, Cut cutaxis);
  260. static void ShrinkBox(ColorBox *box);
  261. static int ComputePalette(LPHISTOGRAM lpHistogram, LPBYTE lp16to8, LPPALETTEENTRY palette);
  262. static COLORREF DetermineRepresentative(ColorBox *box, int palIndex);
  263. static Cut FindSplitAxis(ColorBox *box);
  264. static void SplitBox(ColorBox *box);
  265. static void SortBoxes(void);
  266.  
  267. HANDLE hBoxes;
  268. ColorBox *UsedBoxes;
  269. ColorBox *FreeBoxes;
  270. LPBYTE   glp16to8;
  271.  
  272. //#define hist(r,g,b)  ((DWORD huge *)glpHistogram)[(WORD)(b) | ((WORD)(g)<<IN_DEPTH) | ((WORD)(r)<<(IN_DEPTH*2))]
  273. #define hist(r,g,b)  GetHistogram((BYTE)(r),(BYTE)(g),(BYTE)(b))
  274.  
  275. #pragma optimize ("", off)
  276. //
  277. //  set FS == lpHistogram.sel, so we can get at it quickly!
  278. //
  279. void NEAR PASCAL UseHistogram(LPHISTOGRAM lpHistogram)
  280. {
  281.     _asm {
  282.         mov     ax,word ptr lpHistogram[2]
  283.  
  284.         _emit   08Eh                     ; mov  fs,ax
  285.         _emit   0E0h
  286.     }
  287. }
  288.  
  289. //
  290. //  get the DOWRD histogram count of a RGB
  291. //
  292. DWORD near _fastcall GetHistogram(BYTE r, BYTE g, BYTE b)
  293. {
  294.     if (0)        // avoid compiler warning NO RETURN VALUE
  295.         return 0;
  296.  
  297.     _asm {
  298.         ;
  299.         ; on entry al=r, dl=g, bl=b  [0-31]
  300.         ;
  301.         ; map to a RGB16
  302.         ;
  303.         xor     ah,ah
  304.         shl     ax,5
  305.         or      al,dl
  306.         shl     ax,5
  307.         or      al,bl
  308.  
  309.         ; now ax = RGB16
  310.  
  311.         _emit 66h _asm xor bx,bx           ; xor ebx,ebx
  312.                   _asm mov bx,ax           ; mov  bx,ax
  313.         _emit 66h _asm shl bx,2            ; shl ebx,2
  314.  
  315.         _emit 64h _asm _emit 67h           ; mov dx,fs:[ebx][2]
  316.         _emit 8Bh _asm _emit 53h
  317.         _emit 02h
  318.  
  319.         _emit 64h _asm _emit 67h           ; mov ax,fs:[ebx][0]
  320.         _emit 8Bh _asm _emit 03h
  321.     }
  322. }
  323.  
  324. //
  325. //  increment the histogram count of a RGB16
  326. //
  327. //
  328. //  #define IncHistogram(w) if (lpHistogram[(WORD)(w)] < 0xFFFFFFFF) 
  329. //                              lpHistogram[(WORD)(w)]++;
  330. //
  331. void near _fastcall IncHistogram(WORD rgb16)
  332. {
  333.     _asm {
  334.         ;
  335.         ; on entry ax = rgb16
  336.         ;
  337.         _emit 66h _asm xor bx,bx           ; xor ebx,ebx
  338.                   _asm mov bx,ax           ; mov bx,ax
  339.         _emit 66h _asm shl bx,2            ; shl ebx,2
  340.  
  341.         _emit 64h _asm _emit 67h           ; cmp dword ptr fs:[ebx], -1
  342.         _emit 66h _asm _emit 83h
  343.         _emit 3Bh _asm _emit 0FFh
  344.  
  345.         _emit 74h _asm _emit 05h           ; je  short @f
  346.  
  347.         _emit 64h _asm _emit 67h           ; inc dword ptr fs:[ebx]
  348.         _emit 66h _asm _emit 0FFh
  349.         _emit 03h
  350.     }
  351. }
  352.  
  353. #pragma optimize ("", on)
  354.  
  355. // !!! C8 generates a Jump into the middle of a 2 byte instruction 
  356. // !!! Stupid C8!
  357. #pragma optimize ("", off)
  358.  
  359. //
  360. //  HistogramPalette
  361. //
  362. //  given a histogram, will reduce it to 'nColors' number of colors.
  363. //  returns a optimal palette.  if specifed lp16to8 will contain the
  364. //  translate table from RGB16 to the palette index.
  365. //
  366. //  you can specify lpHistogram as lp16to8
  367. //
  368. HPALETTE HistogramPalette(LPHISTOGRAM lpHistogram, LPBYTE lp16to8, int nColors)
  369. {
  370.     struct {
  371.         WORD         palVersion;
  372.         WORD         palNumEntries;
  373.         PALETTEENTRY palPalEntry[256];
  374.     }   pal;
  375.  
  376.     WORD     w;
  377.     DWORD    dwMax;
  378.     COLORREF rgb;
  379.     ColorBox *box;
  380.     int i;
  381.  
  382.     //
  383.     //  the 'C' code cant handle >64k histogram counts.
  384.     //  !!!fix this
  385.     //
  386.     for (dwMax=0,w=0; w<0x8000; w++)
  387.         dwMax = max(dwMax,lpHistogram[w]);
  388.  
  389.     while (dwMax > 0xFFFFl)
  390.     {
  391.         for (w=0; w<0x8000; w++)
  392.             lpHistogram[w] /= 2;
  393.  
  394.         dwMax /= 2;
  395.     }
  396.  
  397.     if (!InitBoxes(min(nColors, 236)))
  398.         return NULL;
  399.  
  400.     UseHistogram(lpHistogram);
  401.     glp16to8 = lp16to8;
  402.  
  403.     /* while there are free boxes left, split the largest */
  404.  
  405.     i = 0;
  406.  
  407.     do {
  408.        i++;
  409.        SplitBox(UsedBoxes);
  410.        }
  411.     while (FreeBoxes && UsedBoxes->variance);
  412.  
  413.     SortBoxes();
  414.  
  415.     i=0;
  416.  
  417.     //
  418.     // add some standard colors to the histogram
  419.     //
  420.     if (nColors > 236)
  421.     {
  422.         HDC hdc;
  423.  
  424.         hdc = GetDC(NULL);
  425.  
  426.         if (GetDeviceCaps(hdc, RASTERCAPS) & RC_PALETTE)
  427.         {
  428.             GetSystemPaletteEntries(hdc, 0,   10, &pal.palPalEntry[0]);
  429.             GetSystemPaletteEntries(hdc, 246, 10, &pal.palPalEntry[246]);
  430.  
  431.             i = 10;
  432.         }
  433.  
  434.         ReleaseDC(NULL, hdc);
  435.     }
  436.  
  437.     /* Generate the representitives and the associated Palette mapping */
  438.     /* NOTE:  Might loop less than nColors times.                      */
  439.     for (box = UsedBoxes; box; box = box->next, i++)
  440.     {
  441.         rgb = DetermineRepresentative(box, i);
  442.         pal.palPalEntry[i].peRed   = GetRValue(rgb);
  443.         pal.palPalEntry[i].peGreen = GetGValue(rgb);
  444.         pal.palPalEntry[i].peBlue  = GetBValue(rgb);
  445.         pal.palPalEntry[i].peFlags = 0;
  446.     }
  447.  
  448.     DeleteBoxes();
  449.  
  450.     if (nColors > 236)
  451.     {
  452.         for (; i<246; i++)
  453.         {
  454.             pal.palPalEntry[i].peRed   = 0;
  455.             pal.palPalEntry[i].peGreen = 0;
  456.             pal.palPalEntry[i].peBlue  = 0;
  457.             pal.palPalEntry[i].peFlags = 0;
  458.         }
  459.  
  460.         i = 256;
  461.     }
  462.  
  463.     glp16to8 = NULL;
  464.  
  465.     pal.palVersion    = 0x300;
  466.     pal.palNumEntries = i;
  467.     return CreatePalette((LPLOGPALETTE)&pal);
  468. }
  469.  
  470. #pragma optimize ("", on)
  471.  
  472. static void SortBoxes()
  473. {
  474.     ColorBox *box;
  475.     ColorBox *newList;
  476.     ColorBox *insBox;
  477.     ColorBox *nextBox;
  478.  
  479.     newList = UsedBoxes;
  480.     nextBox = newList->next;
  481.     newList->next = NULL;
  482.  
  483.     for (box = nextBox; box; box = nextBox) { // just an insertion sort...
  484.             nextBox = box->next;
  485.             if (box->wt > newList->wt) {
  486.                     box->next = newList;
  487.                     newList = box;
  488.             } else {
  489.                     for (insBox = newList;
  490.                             insBox->next && (box->wt < insBox->next->wt);
  491.                             insBox = insBox->next) ;
  492.                     box->next = insBox->next;
  493.                     insBox->next = box;
  494.             }
  495.     }
  496.  
  497.     UsedBoxes = newList;
  498. }
  499.  
  500.  
  501. /*
  502.    allocate space for nBoxes boxes, set up links.  On exit UsedBoxes
  503.    points to one box, FreeBoxes points to remaining (nBoxes-1) boxes.
  504.    return 0 if successful.
  505. */
  506.  
  507. static BOOL InitBoxes(int nBoxes)
  508. {
  509.     int i;
  510.  
  511.     hBoxes = LocalAlloc(LHND, nBoxes*sizeof(ColorBox));
  512.     if (!hBoxes)
  513.         return FALSE;
  514.  
  515.     UsedBoxes = (ColorBox*)LocalLock(hBoxes);
  516.     FreeBoxes = UsedBoxes + 1;
  517.     UsedBoxes->next = NULL;
  518.  
  519.     for (i = 0; i < nBoxes - 1; ++i)
  520.     {
  521.         FreeBoxes[i].next = FreeBoxes + i + 1;
  522.     }
  523.     FreeBoxes[nBoxes-2].next = NULL;
  524.  
  525.     /* save the bounding box */
  526.     UsedBoxes->rmin = UsedBoxes->gmin = UsedBoxes->bmin = 0;
  527.     UsedBoxes->rmax = UsedBoxes->gmax = UsedBoxes->bmax = IN_SIZE - 1;
  528.     UsedBoxes->variance = 9999999;    /* arbitrary large # */
  529.  
  530.     return TRUE;
  531. }
  532.  
  533. static void DeleteBoxes()
  534. {
  535.    LocalUnlock(hBoxes);
  536.    LocalFree(hBoxes);
  537.    hBoxes = NULL;
  538. }
  539.  
  540. static void SplitBox(ColorBox *box)
  541. {
  542.    /*
  543.       split box into two roughly equal halves and update the data structures
  544.       appropriately.
  545.    */
  546.    Cut cutaxis;
  547.    ColorBox *temp, *temp2, *prev;
  548.  
  549.    cutaxis = FindSplitAxis(box);
  550.        
  551.    /* split the box along that axis.  If rc != 0 then the box contains
  552.       one color, and should not be split */
  553.    if (SplitBoxAxis(box, cutaxis))
  554.       return;
  555.  
  556.    /* shrink each of the boxes to fit the points they enclose */
  557.    ShrinkBox(box);
  558.    ShrinkBox(FreeBoxes);
  559.  
  560.    /* move old box down in list, if necessary */
  561.    if (box->next && box->variance < box->next->variance)
  562.    {
  563.       UsedBoxes = box->next;
  564.       temp = box;
  565.       do {
  566.          prev = temp;
  567.          temp = temp->next;
  568.          } while (temp && temp->variance > box->variance);
  569.       box->next = temp;
  570.       prev->next = box;
  571.    }
  572.  
  573.    /* insert the new box in sorted order (descending), removing it 
  574.       from the free list. */
  575.    if (FreeBoxes->variance >= UsedBoxes->variance)
  576.    {
  577.       temp = FreeBoxes;
  578.       FreeBoxes = FreeBoxes->next;
  579.       temp->next = UsedBoxes;
  580.       UsedBoxes = temp;
  581.    }
  582.    else
  583.    {
  584.       temp = UsedBoxes;
  585.       do {
  586.          prev = temp;
  587.          temp = temp->next;
  588.          } while (temp && temp->variance > FreeBoxes->variance);
  589.       temp2 = FreeBoxes->next;
  590.       FreeBoxes->next = temp;
  591.       prev->next = FreeBoxes;
  592.       FreeBoxes = temp2;
  593.    }
  594. }
  595.  
  596. static Cut FindSplitAxis(ColorBox *box)
  597. {
  598.     unsigned long    proj_r[IN_SIZE],proj_g[IN_SIZE],proj_b[IN_SIZE];
  599.         unsigned long   f;
  600.     double        currentMax,mean;
  601.     unsigned long    w,w1,m,m1;
  602.     short        r,g,b;
  603.     short        bestCut;
  604.     color        bestAxis;
  605.     Cut        cutRet;
  606.     double        temp1,temp2;
  607.     
  608.     for (r = 0; r < IN_SIZE; r++) {
  609.         proj_r[r] = proj_g[r] = proj_b[r] = 0;
  610.     }
  611.     
  612.     w = 0;
  613.     
  614.     // Project contents of box down onto axes
  615.     for (r = box->rmin; r <= box->rmax; r++) {
  616.         for (g = box->gmin; g <= box->gmax; ++g) {
  617.             for (b = box->bmin; b <= box->bmax; ++b) {
  618.                 f = hist(r,g,b);
  619.                 proj_r[r] += f;
  620.                 proj_g[g] += f;
  621.                 proj_b[b] += f;
  622.             }
  623.         }
  624.         w += proj_r[r];
  625.     }
  626.  
  627.     currentMax = 0.0f;
  628.  
  629. #define Check_Axis(l,color)                    \
  630.     m = 0;                            \
  631.     for (l = box->l##min; l <= box->l##max; (l)++) {    \
  632.         m += l * proj_##l[l];                \
  633.     }                            \
  634.     mean = ((double) m) / ((double) w);            \
  635.                                 \
  636.     w1 = 0;                            \
  637.     m1 = 0;                            \
  638.     for (l = box->l##min; l <= box->l##max; l++) {        \
  639.         w1 += proj_##l[l];                \
  640.         if (w1 == 0)                    \
  641.             continue;                \
  642.         if (w1 == w)                    \
  643.             break;                    \
  644.         m1 += l * proj_##l[l];                \
  645.         temp1 = mean - (((double) m1) / ((double) w1));    \
  646.         temp2 = (((double) w1) / ((double) (w-w1))) * temp1 * temp1; \
  647.         if (temp2 > currentMax) {            \
  648.             bestCut = l;                \
  649.             bestAxis = color;            \
  650.             currentMax = temp2;            \
  651.         }                        \
  652.     }
  653.     
  654.     Check_Axis(r,red);
  655.     Check_Axis(g,green);
  656.     Check_Axis(b,blue);
  657.     
  658.     cutRet.cutaxis = bestAxis;
  659.     cutRet.cutpoint = bestCut;
  660.     
  661.     return cutRet;
  662. }
  663.  
  664. static int SplitBoxAxis(ColorBox *box, Cut cutaxis)
  665. {
  666.    /*
  667.       Split box along splitaxis into two boxes, one of which is placed
  668.       back in box, the other going in the first free box (FreeBoxes)
  669.       If the box only contains one color, return non-zero, else return 0.
  670.    */
  671.    ColorBox *next;
  672.  
  673.    if ( box->variance == 0)
  674.       return 1;
  675.  
  676.    /* copy all non-link information to new box */
  677.    next = FreeBoxes->next;
  678.    *FreeBoxes = *box;
  679.    FreeBoxes->next = next;
  680.  
  681.    switch (cutaxis.cutaxis)
  682.    {
  683.       case red:
  684.          box->rmax = cutaxis.cutpoint;
  685.          FreeBoxes->rmin = cutaxis.cutpoint+1;
  686.          break;
  687.       case green:
  688.          box->gmax = cutaxis.cutpoint;
  689.          FreeBoxes->gmin = cutaxis.cutpoint+1;
  690.          break;
  691.       case blue:
  692.          box->bmax = cutaxis.cutpoint;
  693.          FreeBoxes->bmin = cutaxis.cutpoint+1;
  694.          break;
  695.    }
  696.  
  697.    return 0;
  698. }
  699.  
  700. static void ShrinkBox(ColorBox *box)
  701. {
  702.     unsigned long n, sxx, sx2, var, quotient, remainder;
  703.     int r,g,b;
  704.         unsigned long   f;
  705.     unsigned long    proj_r[IN_SIZE],proj_g[IN_SIZE],proj_b[IN_SIZE];
  706.  
  707.     n = 0;
  708.     
  709.     for (r = 0; r < IN_SIZE; r++) {
  710.         proj_r[r] = proj_g[r] = proj_b[r] = 0;
  711.     }
  712.     
  713.     // Project contents of box down onto axes
  714.     for (r = box->rmin; r <= box->rmax; r++) {
  715.         for (g = box->gmin; g <= box->gmax; ++g) {
  716.             for (b = box->bmin; b <= box->bmax; ++b) {
  717.                 f = hist(r,g,b);
  718.                 proj_r[r] += f;
  719.                 proj_g[g] += f;
  720.                 proj_b[b] += f;
  721.             }
  722.         }
  723.         n += proj_r[r];
  724.     }
  725.     
  726.     box->wt = n;
  727.     var = 0;
  728.     
  729. #define AddAxisVariance(c)                        \
  730.     sxx = 0; sx2 = 0;                        \
  731.     for (c = box->c##min; c <= box->c##max; c++) {            \
  732.         sxx += proj_##c[c] * c * c;                \
  733.         sx2 += proj_##c[c] * c;                    \
  734.     }                                \
  735.         quotient = sx2 / n; /* This stuff avoids overflow */        \
  736.         remainder = sx2 % n;                        \
  737.         var += sxx - quotient * sx2 - ((remainder * sx2)/n);
  738.     
  739.     AddAxisVariance(r);
  740.     AddAxisVariance(g);
  741.         AddAxisVariance(b);
  742.  
  743.         box->variance = var;
  744. }
  745.  
  746. static COLORREF DetermineRepresentative(ColorBox *box, int palIndex)
  747. {
  748.    /*
  749.       determines the rgb value to represent the pixels contained in
  750.       box.  nbits is the # bits/component we're allowed to return.
  751.    */
  752.    long f;
  753.    long Rval, Gval, Bval;
  754.    unsigned long total;
  755.    int r, g, b;
  756.    WORD w;
  757.  
  758.    /* compute the weighted sum of the elements in the box */
  759.    Rval = Gval = Bval = total = 0;
  760.    for (r = box->rmin; r <= box->rmax; ++r)
  761.    {
  762.       for (g = box->gmin; g <= box->gmax; ++g)
  763.       {
  764.          for (b = box->bmin; b <= box->bmax; ++b)
  765.          {
  766.             if (glp16to8)
  767.             {
  768.                 w = (WORD)(b) | ((WORD)(g)<<IN_DEPTH) | ((WORD)(r)<<(IN_DEPTH*2));
  769.                 glp16to8[w] = (BYTE)palIndex;
  770.             }
  771.         
  772.             f = hist(r,g,b);
  773.             if (f == 0L)
  774.                continue;
  775.  
  776.             Rval += f * (long) r;
  777.             Gval += f * (long) g;
  778.             Bval += f * (long) b;
  779.  
  780.             total += f;
  781.          }
  782.       }
  783.    }
  784.  
  785.    /* Bias the sum so that we round up at .5 */
  786.    Rval += total / 2;
  787.    Gval += total / 2;
  788.    Bval += total / 2;
  789.  
  790.    return RGB(Rval*255/total/IN_SIZE, Gval*255/total/IN_SIZE, Bval*255/total/IN_SIZE);
  791. }
  792.  
  793. ///////////////////////////////////////////////////////////////////////////////
  794. //
  795. ///////////////////////////////////////////////////////////////////////////////
  796.  
  797.  
  798. ///////////////////////////////////////////////////////////////////////////////
  799. //
  800. //  write this stuff in ASM!
  801. //
  802. ///////////////////////////////////////////////////////////////////////////////
  803.  
  804. void Histogram24(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram)
  805. {
  806.     int x,y;
  807.     BYTE r,g,b;
  808.     WORD w;
  809.  
  810.     UseHistogram(lpHistogram);
  811.  
  812.     WidthBytes -= dx*3;
  813.  
  814.     for (y=0; y<dy; y++)
  815.     {
  816.         for (x=0; x<dx; x++)
  817.         {
  818.             b = *pb++;
  819.             g = *pb++;
  820.             r = *pb++;
  821.             w = RGB16(r,g,b);
  822.             IncHistogram(w);
  823.         }
  824.         pb += WidthBytes;
  825.     }
  826. }
  827.  
  828. void Histogram16(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram)
  829. {
  830.     int x,y;
  831.     WORD w;
  832.  
  833.     UseHistogram(lpHistogram);
  834.  
  835.     WidthBytes -= dx*2;
  836.  
  837.     for (y=0; y<dy; y++)
  838.     {
  839.         for (x=0; x<dx; x++)
  840.         {
  841.             w = *((WORD huge *)pb)++;
  842.             w &= 0x7FFF;
  843.             IncHistogram(w);
  844.         }
  845.         pb += WidthBytes;
  846.     }
  847. }
  848.  
  849. void Histogram8(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors)
  850. {
  851.     int x,y;
  852.     WORD w;
  853.  
  854.     UseHistogram(lpHistogram);
  855.  
  856.     WidthBytes -= dx;
  857.  
  858.     for (y=0; y<dy; y++)
  859.     {
  860.         for (x=0; x<dx; x++)
  861.         {
  862.             w = lpColors[*pb++];
  863.             IncHistogram(w);
  864.         }
  865.         pb += WidthBytes;
  866.     }
  867. }
  868.  
  869. void Histogram4(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors)
  870. {
  871.     int x,y;
  872.     BYTE b;
  873.     WORD w;
  874.  
  875.     UseHistogram(lpHistogram);
  876.  
  877.     WidthBytes -= (dx+1)/2;
  878.  
  879.     for (y=0; y<dy; y++)
  880.     {
  881.         for (x=0; x<(dx+1)/2; x++)
  882.         {
  883.             b = *pb++;
  884.  
  885.             w = lpColors[b>>4];
  886.             IncHistogram(w);
  887.  
  888.             w = lpColors[b&0x0F];
  889.             IncHistogram(w);
  890.         }
  891.         pb += WidthBytes;
  892.     }
  893. }
  894.  
  895. void Histogram1(BYTE huge *pb, int dx, int dy, WORD WidthBytes, LPHISTOGRAM lpHistogram, LPWORD lpColors)
  896. {
  897.     int x,y,i;
  898.     BYTE b;
  899.     WORD w;
  900.  
  901.     UseHistogram(lpHistogram);
  902.  
  903.     WidthBytes -= (dx+7)/8;
  904.  
  905.     for (y=0; y<dy; y++)
  906.     {
  907.         for (x=0; x<(dx+7)/8; x++)
  908.         {
  909.             b = *pb++;
  910.  
  911.             for (i=0; i<8; i++)
  912.             {
  913.                 w = lpColors[b>>7];
  914.                 IncHistogram(w);
  915.                 b<<=1;
  916.             }
  917.         }
  918.         pb += WidthBytes;
  919.     }
  920. }
  921.  
  922. ///////////////////////////////////////////////////////////////////////////////
  923. //
  924. //  write this stuff in ASM! too
  925. //
  926. ///////////////////////////////////////////////////////////////////////////////
  927.  
  928. void Reduce24(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp16to8)
  929. {
  930.     int x,y;
  931.     BYTE r,g,b;
  932.  
  933.     cbOut -= dx;
  934.     cbIn  -= dx*3;
  935.  
  936.     for (y=0; y<dy; y++)
  937.     {
  938.         for (x=0; x<dx; x++)
  939.         {
  940.             b = *pbIn++;
  941.             g = *pbIn++;
  942.             r = *pbIn++;
  943.             *pbOut++ = lp16to8[RGB16(r,g,b)];
  944.         }
  945.         pbIn += cbIn;
  946.         pbOut+= cbOut;
  947.     }
  948. }
  949.  
  950. void Reduce16(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp16to8)
  951. {
  952.     int x,y;
  953.     WORD w;
  954.  
  955.     cbOut -= dx;
  956.     cbIn  -= dx*2;
  957.  
  958.     for (y=0; y<dy; y++)
  959.     {
  960.         for (x=0; x<dx; x++)
  961.         {
  962.             w = *((WORD huge *)pbIn)++;
  963.             *pbOut++ = lp16to8[w&0x7FFF];
  964.         }
  965.         pbIn += cbIn;
  966.         pbOut+= cbOut;
  967.     }
  968. }
  969.  
  970. void Reduce8(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8)
  971. {
  972.     int x,y;
  973.  
  974.     cbIn  -= dx;
  975.     cbOut -= dx;
  976.  
  977.     for (y=0; y<dy; y++)
  978.     {
  979.         for (x=0; x<dx; x++)
  980.         {
  981.             *pbOut++ = lp8to8[*pbIn++];
  982.         }
  983.         pbIn  += cbIn;
  984.         pbOut += cbOut;
  985.     }
  986. }
  987.  
  988. void Reduce4(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8)
  989. {
  990.     int x,y;
  991.     BYTE b;
  992.  
  993.     cbIn  -= (dx+1)/2;
  994.     cbOut -= (dx+1)&~1;
  995.  
  996.     for (y=0; y<dy; y++)
  997.     {
  998.         for (x=0; x<(dx+1)/2; x++)
  999.         {
  1000.             b = *pbIn++;
  1001.             *pbOut++ = lp8to8[b>>4];
  1002.             *pbOut++ = lp8to8[b&0x0F];
  1003.         }
  1004.         pbIn  += cbIn;
  1005.         pbOut += cbOut;
  1006.     }
  1007. }
  1008.  
  1009. void Reduce1(BYTE huge *pbIn, int dx, int dy, WORD cbIn, BYTE huge *pbOut, WORD cbOut, LPBYTE lp8to8)
  1010. {
  1011.     int x,y;
  1012.     BYTE b;
  1013.  
  1014.     cbIn  -= (dx+7)/8;
  1015.     cbOut -= dx;
  1016.  
  1017.     for (y=0; y<dy; y++)
  1018.     {
  1019.         for (x=0; x<dx; x++)
  1020.         {
  1021.             if (x%8 == 0)
  1022.                 b = *pbIn++;
  1023.  
  1024.             *pbOut++ = lp8to8[b>>7];
  1025.             b<<=1;
  1026.         }
  1027.         pbIn  += cbIn;
  1028.         pbOut += cbOut;
  1029.     }
  1030. }
  1031.